package someTestExcemple.huaweiOd.divideAndRecursion;
//华为OD机试 - 找到比自己强的人数 - 递归（Java 2024 E卷 100分）
//https://blog.csdn.net/guorui_java/article/details/142692914
import java.util.*;
public class FindHigherRank {
    // 主函数，从控制台读取输入，并输出结果
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取一行输入，格式如[[2,1][3,2]]
        String input = sc.nextLine().trim();
        // 去掉最外层的中括号
        input = input.substring(1, input.length() - 1);
        // 将相邻的“][”替换为分隔符 "],[" 便于后续拆分
        input = input.replace("][", "],[");

        // 用逗号分隔后的数组存储每个关系
        String[] pairs = input.split("(?<=\\]),\\[");  // 使用正则，注意保留中括号

        // 哈希表存储师徒关系，键为师傅，值为徒弟列表
        Map<Integer, List<Integer>> map = new HashMap<>();
        // 集合存储所有人员
        Set<Integer> people = new HashSet<>();

        // 遍历每个关系对
        for (String pair : pairs) {
            // 去掉可能存在的中括号
            pair = pair.replace("[", "").replace("]", "");
            // 按逗号分隔，得到两个数字
            String[] nums = pair.split(",");
            int master = Integer.parseInt(nums[0]);
            int disciple = Integer.parseInt(nums[1]);
            // 将师傅与徒弟添加到map中
            if (!map.containsKey(master)) {
                map.put(master, new ArrayList<>());
            }
            map.get(master).add(disciple);
            // 添加人员到集合中
            people.add(master);
            people.add(disciple);
        }

        // 将人员排序，按排名从小到大（数值越小越强）
        List<Integer> sortedPeople = new ArrayList<>(people);
        Collections.sort(sortedPeople);

        // 结果数组，用于存储每个人的统计值
        List<Integer> result = new ArrayList<>();
        // 对每个人进行统计：统计其所有下级中比自己强（数值更小）的徒弟数
        for (int person : sortedPeople) {
            int count = dfs(person, map, person);
            result.add(count);
        }

        // 直接输出测试用例格式（无其他描述）
        System.out.println(result);
    }

    // DFS递归函数，返回当前节点所有后代中比当前根节点值小的数量
    public static int dfs(int current, Map<Integer, List<Integer>> map, int rootVal) {
        int count = 0;
        // 如果当前节点没有徒弟，则返回0
        if (!map.containsKey(current)) {
            return count;
        }
        // 遍历所有直接徒弟
        for (int child : map.get(current)) {
            // 如果徒弟比root节点强（数值更小），计数加1
            if (child < rootVal) {
                count++;
            }
            // 递归统计子节点的所有后代
            count += dfs(child, map, rootVal);
        }
        return count;
    }
}
